package class_0904BinarySearchTree;

/**
 * morris遍历：
 * 先往左（走深一点）造环->通过环返回父节点,尝试往右走。-->循环
 */
public class Coding_MorrisTraversal {
    public static class Node{
        int data;
        Node left;
        Node right;
        public Node(int data) {
            this.data = data;
        }
    }

    /**
     *
     * @param head 给定子树的根节点。
     */
    public static void morrisTraversal(Node head){
        while(head!=null){
            //往左走的·逻辑
            Node mostRight = head.left;
            ///左子树存在-找左子树的最右节点，与当前节点连接成环。
            if(mostRight!=null){
                //case1: 未闭合成环， 那么导向就成环。
                //case2: 已成了一次环， 这一次意味着回退检查， 断开连接即可。
                while(mostRight.right!=null && mostRight.right!=head)
                    mostRight = mostRight.right;
                if(mostRight.right==null){
                    mostRight.right = head;//连接闭合成环
                    //继续往左走深搜。
                    head = head.left;
                }
                else{
                    //mostRight.right==head
                    //断环
                    mostRight.right = null;
                    head = head.right;
                }
            }
            else{
                head = head.right;
            }
        }
    }
    //morris处理先序遍历。
    public static void morrisPre(Node head){
        while(head!=null){
            Node mostRight = head.left;
            if(mostRight!=null){
                while(mostRight.right!=null && mostRight.right!=head)
                    mostRight = mostRight.right;
                if(mostRight.right==null){
                    mostRight.right = head;
                    //处理，这里是打印
                    System.out.print(head.data+" ");
                    head = head.left;
                }
                if(mostRight.right==head){
                    mostRight.right = null;
                    head = head.right;
                }
            }
            else{
                //处理-打印。
                System.out.print(head.data+" ");
                head = head.right;
            }
        }
    }

    public static void morrisIn(Node head) {
        // 当节点不为空时进入循环
        while (head != null) {
            // 1. 找到当前节点head的左子树的最右节点mostRight
            Node mostRight = head.left;

            // 如果存在左子树
            if (mostRight != null) {
                // 2. 寻找左子树的最右节点，即当前节点head左子树的最右端节点
                while (mostRight.right != null && mostRight.right != head) {
                    mostRight = mostRight.right;
                }
                // 3. 如果最右节点的右指针为空，将其指向当前节点head，用于回溯
                if (mostRight.right == null) {
                    mostRight.right = head;
                    // 当前节点移动到左子节点，继续处理左子树
                    head = head.left;
                }
                // 4. 如果最右节点的右指针已经指向当前节点head，说明左子树已遍历完毕
                else {
                    // 5. 恢复树的结构，将最右节点的右指针设为null
                    mostRight.right = null;
                    // 打印当前节点值
                    System.out.print(head.data + " ");
                }
            }
            // 如果没有左子树，直接处理当前节点并移动到右子节点
            else {
                System.out.print(head.data + " ");
            }
            // 移动到当前节点的右子节点
            head = head.right;
        }
    }

}
